﻿//#include <iostream>
//#include <string>
//using namespace std;
//int main()
//{
//	string s;
//	int hash[26] = { 0 };
//	char ret = 0;
//	int maxCount = 0;
//
//	while (cin >> s)
//	{
//		for (auto ch : s)
//		{
//			if (++hash[ch - 'a'] > maxCount)
//			{
//				ret = ch;
//				maxCount = hash[ch - 'a'];
//			}
//		}
//	}
//
//	cout << ret << endl;
//
//	return 0;
//}




//#include <iostream>
//#include <vector>
//#include <string>
//#include <queue>
//using namespace std;
//int main()
//{
//	string s;
//	while (cin >> s)
//	{
//		// 1. 先统计每个字符的频次
//		int hash[300] = { 0 };
//		for (auto ch : s)
//		{
//			hash[ch]++;
//		}
//		// 2. 把所有的频次放⼊堆⾥⾯
//		priority_queue<int, vector<int>, greater<int>> heap;
//		for (int i = 0; i < 300; i++)
//		{
//			if (hash[i]) heap.push(hash[i]);
//		}
//		// 3. 哈夫曼编码
//		int ret = 0;
//		while (heap.size() > 1)
//		{
//			int t1 = heap.top(); heap.pop();
//			int t2 = heap.top(); heap.pop();
//			ret += t1 + t2;
//			heap.push(t1 + t2);
//		}
//		cout << ret << endl;
//	}
//	return 0;
//}




#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e4 + 10;
int n;
int dp[N];
int main()
{
	cin >> n;
	memset(dp, 0x3f, sizeof dp);
	dp[0] = 0;
	for (int i = 1; i * i <= n; i++)
	{
		for (int j = i * i; j <= n; j++)
		{
			dp[j] = min(dp[j], dp[j - i * i] + 1);
		}
	}
	cout << dp[n] << endl;
	return 0;
}